package kyssion.leetcode.num101_150;

import kyssion.leetcode.util.Node;

public class code116_填充每个节点的下一个右侧节点指针 {

    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        ans(root);
        return root;
    }

    private void ans(Node root) {
        if (root == null) {
            return;
        }
        ans(root.left);
        ans(root.right);
        createLeftAndRight(root.left, root.right, 0);
    }

    private void createLeftAndRight(Node left, Node right, int deep) {
        if (left == null || right == null) {
            return;
        }
        if (left.next != null) {
            createLeftAndRight(left.left, right, deep + 1);
            createLeftAndRight(left.right, right, deep + 1);
        } else {
            left.next = findMaxLeft(right, 0, deep);
            createLeftAndRight(left.left, right, deep + 1);
            createLeftAndRight(left.right, right, deep + 1);
        }
    }

    private Node findMaxLeft(Node right, int i, int deep) {
        if (right == null) {
            return null;
        }
        if (i == deep) {
            return right;
        }

        Node left = findMaxLeft(right.left, i + 1, deep);
        if (left != null) {
            return left;
        }

        return findMaxLeft(right.right, i + 1, deep);
    }


    /**
     * 这个算法设计的很巧妙,利用了之前root节点的next ,
     * 我要计算root节点的下一位最右侧的next 其实就是root的next节点的最左侧
     * 利用这道理可以很轻松的递归了
     * @param root
     * @return
     */
    public Node connect2(Node root) {
        addNext(root);
        return root;
    }

    private void addNext(Node node) {
        if (node == null)
            return;
        if (node.left == null && node.right == null)
            return;
        if (node.left != null && node.right != null) {
            node.left.next = node.right;
        }
        Node next_node, p;
        next_node = null;
        p = node.next;
        while (p != null) {
            if (p.left != null) {
                next_node = p.left;
                break;
            } else if (p.right != null) {
                next_node = p.right;
                break;
            } else
                p = p.next;
            ;
        }
        if(next_node!=null)
        {
            if (node.right != null) {
                node.right.next = next_node;
            } else {
                node.left.next = next_node;
            }
        }
        addNext(node.right);
        addNext(node.left);
    }
}
